//
//  Demo2.c
//  Math06
//
//  Created by Xavier on 2023/11/15.
//

#include <stdio.h>
#include <stdlib.h>
//2.编写高级语言程序，实现约瑟夫环问题。
//设编号为1，2，……n得n个人围坐一圈，约定编号为k（k=1）的人从1开始报数，数到m的那个人出列。它的下一位继续从1开始报数，数到m的人出列，依次类推，直到所有人都出列为止

//循环链表实现

typedef struct node_t
{
    int data;
    struct node_t *next;
}link_node_t,*link_list_t;
 
int main(int argc, const char *argv[])
{
    link_list_t h=NULL;    //用于指向头结点
    link_list_t pdel=NULL;    //用于指向被删除节点
    link_list_t ptail=NULL;   //用于指向当前链表的尾
    link_list_t pnew=NULL;    //用于指向新创建的节点
    int kill_num;             //数到几淘汰猴子
    int start_num;            //从几号猴子开始
    int all_sum;              //总数
    printf("please input monkey all_sum:");
    scanf("%d",&all_sum);
    printf("please input start_num:");
    scanf("%d",&start_num);
    printf("please input monkey kill_num:");
    scanf("%d",&kill_num);
 
    h=(link_list_t)malloc(sizeof(link_node_t));
    if(h==NULL)
    {
        printf("error");
        return -1;
    }
    h->data=1;
    h->next=NULL;
    ptail=h;         //尾指针指向当前第一个节点
    for(int i=2;i<=all_sum;i++)
    {
 
        pnew=(link_list_t)malloc(sizeof(link_node_t));
        if(pnew==NULL)  //创建新节点
        {
            printf("error");
            return -1;
        }
 
        pnew->data=i;     //为新节点赋值
        pnew->next=NULL;
 
        ptail->next=pnew;   //将新节点连接到链表尾部
        ptail=pnew;         //尾指针跟随移动到尾部
 
    }
 
    ptail->next=h;           //将头指针保存到链表尾部，形成单向循环链表
 
 
    //开始淘汰猴子
    for(int i=0;i<start_num-1;i++)   //将头指针移动到开始的猴子号码处
        h=h->next;
    //循环进行淘汰猴子
    while(h!=h->next)  //条件不成的时候，就剩一个猴子,只有一个节点
    {
        for(int i=0;i<kill_num-2;i++)     //将头指针移动到即将删除节点的前一个节点
            h=h->next;
 
        pdel=h->next;
        h->next=pdel->next;                  //跨过删除节点
        printf("kill %d\n",pdel->data);      //打印被淘汰的猴子
        free(pdel);
        pdel=NULL;
        h=h->next;   //淘汰该猴子后，从下一个节点开始继续开始数,将头指针移动到开始数的地方
    }
    printf("king is %d\n",h->data);         //国王诞生
    return 0;
}
                                                                


